package com.zhu.solution.arrayQuestion;

import java.util.HashSet;
import java.util.Set;

/**
 * 只出现一次的数字
 *
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 *
 * 说明：
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 *
 */
public class Solution_5 {
    public static void main(String[] args) {
        int[] nums = {1,1,2,2,3,7,5,5,6,6,4,4,7};
        int b = new Solution_5().singleNumber_2(nums);
        System.out.println(b);


        System.out.println(5^2);
        System.out.println(5^7);
        System.out.println(5^7^5);
        System.out.println(5^5);
    }

    public int singleNumber(int[] nums) {
        int sum = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums){
            if (set.add(num)){//如果元素不重复时，加
                sum += num;
            }else {//否则，元素重复时，减
                sum -= num;
            }
        }
        //最后的结果为不重复的元素
        return sum;
    }

    //异或运算
    public int singleNumber_2(int[] nums) {
        int reduce = 0;
        for (int num : nums) {
            reduce =  reduce ^ num;
        }
        return reduce;
    }
}

/*
* 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

*
*
*
* */
